package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreePrinter;
import com.example.leetcode.tree.common.TreeUtils;

/**
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 *
 *
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 * 解释: 二叉树不包含值为 0 的节点
 * 示例 3:
 *
 * 输入: root = [], key = 0
 * 输出: []
 *
 *
 * 提示:
 *
 * 节点数的范围 [0, 104].
 * -105 <= Node.val <= 105
 * 节点值唯一
 * root 是合法的二叉搜索树
 * -105 <= key <= 105
 *
 *
 * 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
 */
public class leetcode450 {
    public static void main(String[] args) {
        Integer[] nums = {5, 3, 6, 2, 4, null, 7};
        int key = 3;

        TreeNode root = TreeUtils.generateLeetcodeTree(nums);
        TreePrinter.printPrettyTree(root);

        Solution solution = new Solution();
        TreeNode result = solution.deleteNode(root, key);
        TreeUtils.printTree(result);
    }

    /**
     * 删除节点有三种情况：
     *
     * 目标节点是叶子节点：直接删除即可。
     *
     * 目标节点只有一个子节点：用子节点替代当前节点。
     *
     * 目标节点有两个子节点：找右子树中最小的节点（即中序后继）或左子树中最大的节点（中序前驱），用其替代当前节点，然后递归删除中序后继/前驱。
     */
    static class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return null;

            if (key < root.val) {
                root.left = deleteNode(root.left, key);
            } else if (key > root.val) {
                root.right = deleteNode(root.right, key);
            } else {
                // 找到要删除的节点
                if (root.left == null) return root.right;
                if (root.right == null) return root.left;

                // 两个子节点都不为空：用右子树的最小节点替换当前节点
                TreeNode minNode = getMin(root.right);
                // 直接替换为新值
                root.val = minNode.val;
                // 然后删除右子树的最小值节点
                root.right = deleteNode(root.right, minNode.val);
            }

            return root;
        }

        private TreeNode getMin(TreeNode node) {
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
    }


}
